Lecture 15_ Cryptography.md (5695B)
1 +++ 2 title = 'Lecture 15: Cryptography' 3 template = 'page-math.html' 4 +++ 5 6 # Lecture 15: Cryptography 7 8 Allows secure comms between parties when an attacker can intercept/modify their messages. 9 Goals: 10 - confidentiality: message between parties can't be read 11 - in apps, ideal is end-to-end encryption (only sender and recipient have key) 12 - integrity: message between parties can't be changed without them finding out 13 - in apps, digital signatures (not valid if message or sender changes) 14 - authentication: attacker can't impersonate a party 15 - non-repudiation: a party can't deny that they sent a message 16 - use asymmetric digital signatures 17 18 Terms: 19 - plaintext: readable text to be transmitted 20 - ciphertext: unreadable text actually sent 21 - encryption: converting plaintext into ciphertext 22 - decryption: recovering plaintext from ciphertext 23 24 Kerckhoffs' Principle: when encrypting, separate algorithm from key. Assume attacker knows algorithm, keep key secret 25 26 Caesar cipher: shift letters in alphabet by a fixed amount 27 - attacks: bruteforce, frequency analysis (some letters more common in natural languages) 28 29 Cryptographic hashes: 30 - hash function maps message (arbitrary length) to hash (fixed length), should be computationally hard to reverse 31 - often used to identify message, because it's hard to find message with same hash 32 - properties: 33 - pre-image resistance: given hash, hard to find message that hashes to it 34 - second pre-image resistance: given message, it's hard to find another message with the same hash 35 - collision resistance: hard to find any two messages that have the same hash 36 - well-known types: old and insecure (MD5, SHA-1), SHA-2, SHA-3 37 38 Random numbers: 39 - CPUs are deterministic so can't generate truly random numbers 40 - Pseudo-random number generator (PRNG) computes number from seed, which is updated for every generated number 41 42 Blockchain: 43 - Bitcoin: decentralised digital currency using blockchain 44 - each block of transactions contains hash of previous block, so can't change past transactions without changing later ones 45 - real chain is what more than 50% of users agree on 46 47 Perfect encryption: 48 - never reuse the key 49 - key is perfectly random 50 - no information is leaked from ciphertext 51 52 ## Symmetric cryptography 53 Uses single key to encrypt and decrypt. 54 Properties: 55 - provides confidentiality 56 - signature schemes provide integrity and authentication 57 58 One-time pad: 59 - assume we have message and key both with n bits 60 - encrypt: ciphertext = msg ⨁ key 61 - decrypt: msg = ciphertext ⨁ key 62 - holds because ciphertext ⨁ key = msg ⨁ key ⨁ key = msg ⨁ 0 63 - provides perfect encryption because doesn't leak any information (0 bit could be 0⨁0 or 1⨁1 with equal probability) 64 - breaks if key is reused 65 66 Stream ciphers: 67 - use PRNG to generate key for one-time pad 68 - initial seed becomes real key 69 70 Block ciphers: 71 - divide data in blocks 72 - perform computation using key to map plain block into cipher block 73 74 Cipher block chaining: 75 - make each block depend on the previous one 76 - for first block, use initialization vector instead (doesn't have to be secret, shouldn't be reused) 77 78 Padding: 79 - if message sizes not multiple of block size, must be padded 80 - don't add zeros, because impossible to recover original if it ends with zeros 81 - instead, pad with bytes containing padding length 82 83 Signatures: 84 - message authentication code is signature for message 85 - combine key with message and apply hash function 86 - key needed to generate and to validate code 87 - provides integrity and authentication, but not non-repudiation (any verifier can sign) 88 89 ## Asymmetric cryptography 90 Uses two keys: anyone encrypts with public key, only owner decrypts with private key 91 92 RSA: 93 - sender generates public and private key together 94 - public key available to anyone, private key kept secret 95 - mathematically not viable to derive d from e 96 - to generate key, generate large number _m_, public key _e_, private key _d_ such that: $(n^{e})^{d} = n \enspace (\text{mod $m$})$ for any _n_ 97 - relies on difficulty of writing _m_ as product of prime number factors 98 - special random padding 99 - only works for data that fits inside key size 100 - signatures: 101 - to sign, compute hash of message and encrypt hash with private key 102 - to verify, compute hash of message and decrypt with signer's public key, then compare with encrypted hash received from signer 103 104 ## Key management 105 Symmetric: key distribution center: 106 - one trusted party which shares symmetric keys with all others 107 - Kerberos is a system for key communication, but need constant access to center and is single point of failure 108 - possible to establish key without sending any revealing info (e.g. Diffie-Hellman Key Exchange) 109 110 Asymmetric: 111 - Certification Authority (CA) 112 - issues certificates, keeps revocation list of certificates that may be compromised 113 - X5.09 certificates containing e.g. identity of holder, public key of holder, expiration date, signature from CA 114 - verifies identities of users 115 - typically company that must be trusted 116 - Self-signed certificate: 117 - signed with own private key 118 - can be made by anyone so not trusted by default 119 120 ## SSL and HTTPS 121 SSL (Secure Sockets Layer) ensures crypto protection for network connection on top of TCP (aka TLS) 122 Goals: 123 - end-to-end encryption, Diffie-Hellman to create shared key 124 - authenticates using X5.09 certificate (prevents MITM attack) 125 - typically doesn't authenticate client 126 127 ## Password storage 128 Hash password when storing. 129 130 Bruteforce solutions: 131 1. Use salted hash: 132 - when storing password, generate random string and concatenate with password before hashing 133 - store salt with hash. 134 2. Use slow hash: e.g. apply hash 1000 times 135